{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of People to Teach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTeachings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #需要教语言的最少人数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个由 <code>m</code> 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，数组 <code>languages</code> 和数组 <code>friendships</code> ，它们的含义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>总共有 <code>n</code> 种语言，编号从 <code>1</code> 到 <code>n</code> 。</li>\n",
    "\t<li><code>languages[i]</code> 是第 <code>i</code> 位用户掌握的语言集合。</li>\n",
    "\t<li><code>friendships[i] = [u<sub>​​​​​​i</sub>​​​, v<sub>​​​​​​i</sub>]</code> 表示 <code>u<sup>​​​​​</sup><sub>​​​​​​i</sub></code>​​​​​ 和 <code>v<sub>i</sub></code> 为好友关系。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以选择 <strong>一门</strong> 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 <strong>最少</strong> 需要教会多少名用户。</p>\n",
    "请注意，好友关系没有传递性，也就是说如果 <code>x</code> 和 <code>y</code> 是好友，且 <code>y</code> 和 <code>z</code> 是好友， <code>x</code> 和 <code>z</code> 不一定是好友。\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>教用户 1 和用户 3 第三门语言，需要教 2 名用户。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 500</code></li>\n",
    "\t<li><code>languages.length == m</code></li>\n",
    "\t<li><code>1 <= m <= 500</code></li>\n",
    "\t<li><code>1 <= languages[i].length <= n</code></li>\n",
    "\t<li><code>1 <= languages[i][j] <= n</code></li>\n",
    "\t<li><code>1 <= u<sub>​​​​​​i</sub> < v<sub>​​​​​​i</sub> <= languages.length</code></li>\n",
    "\t<li><code>1 <= friendships.length <= 500</code></li>\n",
    "\t<li>所有的好友关系 <code>(u<sub>​​​​​i, </sub>v<sub>​​​​​​i</sub>)</code> 都是唯一的。</li>\n",
    "\t<li><code>languages[i]</code> 中包含的值互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-people-to-teach](https://leetcode.cn/problems/minimum-number-of-people-to-teach/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-people-to-teach](https://leetcode.cn/problems/minimum-number-of-people-to-teach/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[[1],[2],[1,2]]\\n[[1,2],[1,3],[2,3]]', '3\\n[[2],[1,3],[1,2],[3]]\\n[[1,4],[1,2],[3,4],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        yu = [0] +languages   \n",
    "        def cao(x,y):\n",
    "            for v in yu[x]:\n",
    "                if v in yu[y]:return False\n",
    "            return True\n",
    "        s=set()\n",
    "        for a,b in friendships:\n",
    "            if cao(a,b):\n",
    "                s.add(a)\n",
    "                s.add(b)\n",
    "        if not s:return 0\n",
    "        c=Counter()\n",
    "        for w in s:c+= Counter(yu[w])  \n",
    "        return len(s) -c.most_common(1)[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(\n",
    "        self, n: int, languages: List[List[int]], friendships: List[List[int]]\n",
    "    ) -> int:\n",
    "        def has_common(x, y):\n",
    "            return len(set(x) & set(y)) > 0\n",
    "\n",
    "        no_common = set()\n",
    "        for x, y in friendships:\n",
    "            if not has_common(languages[x - 1], languages[y - 1]):\n",
    "                no_common.add(x)\n",
    "                no_common.add(y)\n",
    "        # print(no_common)\n",
    "\n",
    "        if not no_common:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        lang_cnt = [0] * n\n",
    "        for x in no_common:\n",
    "            for lang in languages[x - 1]:\n",
    "                temp = lang_cnt[lang - 1] + 1\n",
    "                lang_cnt[lang - 1] = temp\n",
    "                if temp > res:\n",
    "                    res = temp\n",
    "\n",
    "        return len(no_common) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        s=set()\n",
    "        for i,j in friendships:\n",
    "            if not set(languages[i-1])&set(languages[j-1]):\n",
    "                s.add(i-1)\n",
    "                s.add(j-1)\n",
    "        if not s:\n",
    "            return 0\n",
    "        cnt=Counter()\n",
    "        for i in s:\n",
    "            cnt+=Counter(languages[i])\n",
    "        return len(s)-cnt.most_common(1)[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        yu = [0] +languages   \n",
    "        def cao(x,y):\n",
    "            for v in yu[x]:\n",
    "                if v in yu[y]:return False\n",
    "            return True\n",
    "        s=set()\n",
    "        for a,b in friendships:\n",
    "            if cao(a,b):\n",
    "                s.add(a)\n",
    "                s.add(b)\n",
    "        if not s:return 0\n",
    "        c=Counter()\n",
    "        for w in s:c+= Counter(yu[w])  \n",
    "        return len(s) -c.most_common(1)[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        s=set()\n",
    "        for i,j in friendships:\n",
    "            if not set(languages[i-1])&set(languages[j-1]):\n",
    "                s.add(i-1)\n",
    "                s.add(j-1)\n",
    "        if not s:\n",
    "            return 0\n",
    "        cnt=Counter()\n",
    "        for i in s:\n",
    "            cnt+=Counter(languages[i])\n",
    "        return len(s)-sorted(cnt.values(),reverse=True)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(\n",
    "        self, n: int, languages: List[List[int]], friendships: List[List[int]]\n",
    "    ) -> int:\n",
    "        def has_common(x, y):\n",
    "            return len(set(x) & set(y)) > 0\n",
    "\n",
    "        no_common = set()\n",
    "        for x, y in friendships:\n",
    "            if not has_common(languages[x - 1], languages[y - 1]):\n",
    "                no_common.add(x)\n",
    "                no_common.add(y)\n",
    "        # print(no_common)\n",
    "\n",
    "        if not no_common:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        lang_cnt = [0] * n\n",
    "        for x in no_common:\n",
    "            for lang in languages[x - 1]:\n",
    "                lang_cnt[lang - 1] = lang_cnt[lang - 1] + 1\n",
    "                res = max(res, lang_cnt[lang - 1])\n",
    "\n",
    "        return len(no_common) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        # 把和与好友有沟通障碍的人统计出来\n",
    "        # 然后统计这些有沟通障碍的人的学的最多的语言是什么\n",
    "        # 然后用有沟通障碍的总数去减去最多的语言是什么\n",
    "        def is_valid(x,y):\n",
    "            for x1 in languages[x-1]:\n",
    "                for y1 in languages[y-1]:\n",
    "                    if x1 == y1:return True\n",
    "            return False\n",
    "        no_common = set()\n",
    "        for x,y in friendships:\n",
    "            # 如果有沟通障碍\n",
    "            if not is_valid(x,y):\n",
    "                no_common.add(x)\n",
    "                no_common.add(y)\n",
    "        if len(no_common) == 0:\n",
    "            return 0\n",
    "        # 统计最多\n",
    "        cnt = defaultdict(int)\n",
    "        for x in no_common:\n",
    "            for l in languages[x-1]:\n",
    "                cnt[l] += 1\n",
    "        most = max(cnt.values())\n",
    "        return len(no_common) - most"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        \n",
    "        nocom=set()\n",
    "        for s,e in friendships:\n",
    "            a=languages[s-1]\n",
    "            b=languages[e-1]\n",
    "            if len(set(a)|set(b))==(len(a)+len(b)):\n",
    "                nocom.add(s)\n",
    "                nocom.add(e)\n",
    "        lan=[]\n",
    "        if len(nocom)==0:\n",
    "            return 0\n",
    "        for x in nocom:\n",
    "            lan=lan+languages[x-1]\n",
    "        cnt=collections.Counter(lan)\n",
    "        ans=len(nocom)-max(cnt.values())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        tag = [0] * (n + 1)\n",
    "        b = set()\n",
    "        for u,v in friendships:\n",
    "            s = set(languages[u-1])\n",
    "            r = True\n",
    "            for g in languages[v-1]:\n",
    "                if g in s:\n",
    "                    r = False\n",
    "                    break\n",
    "            if r:\n",
    "                b.add(u)\n",
    "                b.add(v)\n",
    "        for a in b:\n",
    "            for t in languages[a-1]:\n",
    "                tag[t] += 1\n",
    "        a = max(tag)\n",
    "        return len(b) -a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        language_dict = dict()\n",
    "\n",
    "        def can_talk(languages_, p1_, p2_):\n",
    "            # print(p1_, p2_)\n",
    "            if len(list(set(languages_[p1_-1]).intersection(set(languages_[p2_-1])))) > 0:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        no_language = True\n",
    "        intersect_language_set = None\n",
    "        no_common = set()\n",
    "        for fs in friendships:\n",
    "            if not can_talk(languages, fs[0], fs[1]):\n",
    "                no_common.add(fs[0]-1)\n",
    "                no_common.add(fs[1]-1)\n",
    "        cnt_dict = dict()\n",
    "        for people in no_common:\n",
    "            for language in languages[people]:\n",
    "                if language not in cnt_dict.keys():\n",
    "                    cnt_dict[language] = 0\n",
    "                cnt_dict[language] += 1\n",
    "        \n",
    "        most_popular = 0\n",
    "        for key in cnt_dict.keys():\n",
    "            if cnt_dict[key] > most_popular:\n",
    "                most_popular = cnt_dict[key]\n",
    "\n",
    "        return len(no_common) - most_popular\n",
    "\n",
    "\n",
    "        #         no_language = False\n",
    "\n",
    "        #         new_intersect_language_set = set(languages[fs[0]-1]+languages[fs[1]-1])\n",
    "        #         print(fs[0], fs[1], new_intersect_language_set)\n",
    "        #         if intersect_language_set is None:\n",
    "        #             intersect_language_set = new_intersect_language_set.copy()\n",
    "        #         else:\n",
    "        #             intersect_language_set = intersect_language_set.intersection(new_intersect_language_set)\n",
    "\n",
    "        #         for l in languages[fs[0]-1]:\n",
    "        #             if l in intersect_language_set:\n",
    "        #                 if l not in language_dict.keys():\n",
    "        #                     language_dict[l] = set()\n",
    "        #                 language_dict[l].add(fs[1])\n",
    "        #         for l in languages[fs[1]-1]:\n",
    "        #             if l in intersect_language_set:\n",
    "        #                 if l not in language_dict.keys():\n",
    "        #                     language_dict[l] = set()\n",
    "        #                 language_dict[l].add(fs[0])\n",
    "\n",
    "        # if no_language:\n",
    "        #     return 0\n",
    "        # print(intersect_language_set)\n",
    "        # print(language_dict)\n",
    "        # min_people = sys.maxsize\n",
    "        # for key in language_dict.keys():\n",
    "        #     if key in intersect_language_set:\n",
    "        #         if len(language_dict[key]) < min_people:\n",
    "        #             min_people = len(language_dict[key])\n",
    "\n",
    "        # return min_people\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        # O(n**2)\n",
    "        def is_valid(x,y):\n",
    "            for x1 in languages[x-1]:\n",
    "                for y1 in languages[y-1]:\n",
    "                    if x1 == y1:return True\n",
    "            return False\n",
    "        no_common = set()\n",
    "        # O(m)\n",
    "        for x,y in friendships:\n",
    "            if not is_valid(x,y):\n",
    "                no_common.add(x)\n",
    "                no_common.add(y)\n",
    "        if len(no_common) == 0:return 0\n",
    "        cnt = defaultdict(int)\n",
    "        for x in no_common:\n",
    "            for l in languages[x-1]:\n",
    "                cnt[l] += 1\n",
    "        most = max(cnt.values())\n",
    "        return len(no_common) - most"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        d = defaultdict(set)\n",
    "        numd = set()\n",
    "        for f1, f2 in friendships:\n",
    "            if set(languages[f1-1]) & set(languages[f2-1]):\n",
    "                continue\n",
    "            for li in languages[f1-1]:\n",
    "                d[li].add(f1)\n",
    "            for li in languages[f2-1]:\n",
    "                d[li].add(f2)\n",
    "            numd.add(f1)\n",
    "            numd.add(f2)\n",
    "\n",
    "        huimax = 0\n",
    "        for key, v in d.items():\n",
    "            if len(v) > huimax:\n",
    "                huimax = len(v)\n",
    "        return len(numd) - huimax\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        m = len(languages)\n",
    "        mat = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in languages[i-1]:\n",
    "                mat[i][j] = 1 \n",
    "        g = [] \n",
    "        people = set()\n",
    "        for i, [a, b] in enumerate(friendships):\n",
    "            flag = 0 \n",
    "            for j in range(1,n+1):\n",
    "                if mat[a][j] == mat[b][j] == 1:\n",
    "                    flag = 1 \n",
    "                    break \n",
    "            if flag == 0:\n",
    "                #g.append([a,b])\n",
    "                people.add(a)\n",
    "                people.add(b) \n",
    "        #print(people)\n",
    "        #print(g) \n",
    "        ans = float('inf')\n",
    "        for j in range(1, n+1):\n",
    "            #cmat = copy.deepcopy(mat) \n",
    "            cnt  = 0 \n",
    "            for i in people:\n",
    "                if mat[i][j] == 0:\n",
    "                    #cmat[i][j] = 1\n",
    "                    cnt += 1 \n",
    "            \n",
    "            ans = min(ans, cnt) \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        m = len(languages)\n",
    "        lang = [[False]*(n+1) for _ in range(m+1)]\n",
    "        for i,lan_list in enumerate(languages, start=1):\n",
    "            for lan in lan_list:\n",
    "                lang[i][lan] = True\n",
    "        \n",
    "        unconnect = set()\n",
    "        for u,v in friendships:\n",
    "            flag = True\n",
    "            for i in range(1,n+1):\n",
    "                if lang[u][i] and lang[v][i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                unconnect.add(u)\n",
    "                unconnect.add(v)\n",
    "\n",
    "        if len(unconnect)==0:\n",
    "            return 0\n",
    "\n",
    "        cnt = defaultdict(int)\n",
    "        for user in unconnect:\n",
    "            for i in range(1,n+1):\n",
    "                if lang[user][i]:\n",
    "                    cnt[i]+=1\n",
    "\n",
    "        vlist = [v for k,v in cnt.items()]\n",
    "        max_v = 0\n",
    "        for v in vlist:\n",
    "            if v>max_v:\n",
    "                max_v = v\n",
    "\n",
    "        return len(unconnect) - max_v\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        m = len(languages) \n",
    "        mat = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i, vec in enumerate(languages):\n",
    "            for j in vec:\n",
    "                mat[i+1][j] = 1 \n",
    "        pset = set() \n",
    "        for a,b in friendships:\n",
    "            flag = 0 \n",
    "            for j in range(1,n+1):\n",
    "                if mat[a][j] == mat[b][j] == 1:\n",
    "                    flag = 1 \n",
    "                    break \n",
    "            if flag == 0:\n",
    "                pset.add(a)\n",
    "                pset.add(b) \n",
    "        ans = float('inf')\n",
    "        for j in range(1, n+1):\n",
    "            cnt = 0 \n",
    "            for i in pset:\n",
    "                if mat[i][j] == 0:\n",
    "                    cnt+=1\n",
    "            if cnt < ans:\n",
    "                ans = cnt \n",
    "        return ans if ans < float('inf') else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        m = len(languages)\n",
    "        languages = [set(lang) for lang in languages]\n",
    "        mapping = {}\n",
    "        peoples = set()\n",
    "        maxcnt = 0\n",
    "        for a, b in friendships:\n",
    "            if(len(languages[a-1] & languages[b-1]) == 0):\n",
    "                if(a-1 not in peoples):\n",
    "                    peoples.add(a-1)\n",
    "                    for c in languages[a-1]:\n",
    "                        if(c not in mapping):\n",
    "                            mapping[c] = 0\n",
    "                        mapping[c] += 1\n",
    "                        maxcnt = max(maxcnt,mapping[c])\n",
    "                if(b-1 not in peoples):\n",
    "                    peoples.add(b-1)\n",
    "                    for c in languages[b-1]:\n",
    "                        if(c not in mapping):\n",
    "                            mapping[c] = 0\n",
    "                        mapping[c] += 1\n",
    "                        maxcnt = max(maxcnt,mapping[c])\n",
    "        return len(peoples) - maxcnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "贪心\n",
    "找到不能相互沟通的所有好友关系, 在好友关系中的所有用户都需要学会同一门语言才可以沟通. \n",
    "将好友关系中的所有用户已经学会的语言进行计数, 最多用户已经学会的语言就是最少需要学会用户的数量。\n",
    "'''\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        l = len(languages)\n",
    "        res = [0 for i in range(n)] # 语言计数\n",
    "        languages = [set(i) for i in languages]\n",
    "        s = set() # 存在无法沟通关系的用户\n",
    "        for i, j in friendships:\n",
    "            if languages[i - 1] & languages[j - 1]: # 如果可以沟通就不需要进行统计\n",
    "                continue\n",
    "            s.add(i)\n",
    "            s.add(j)\n",
    "        for i in s:\n",
    "            for j in languages[i - 1]:#对语言进行计数\n",
    "                res[j - 1] += 1\n",
    "        return len(s) - max(res)#用户总数减去已会语言最大值就是需要学会同一门语言的最少用户数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        m = len(languages)\n",
    "        languages = [set(lang) for lang in languages]\n",
    "        mapping = {}\n",
    "        peoples = set()\n",
    "        maxcnt = 0\n",
    "        for a, b in friendships:\n",
    "            if(len(languages[a-1] & languages[b-1]) == 0):\n",
    "                if(a-1 not in peoples):\n",
    "                    peoples.add(a-1)\n",
    "                    for c in languages[a-1]:\n",
    "                        if(c not in mapping):\n",
    "                            mapping[c] = 0\n",
    "                        mapping[c] += 1\n",
    "                        maxcnt = max(maxcnt,mapping[c])\n",
    "                if(b-1 not in peoples):\n",
    "                    peoples.add(b-1)\n",
    "                    for c in languages[b-1]:\n",
    "                        if(c not in mapping):\n",
    "                            mapping[c] = 0\n",
    "                        mapping[c] += 1\n",
    "                        maxcnt = max(maxcnt,mapping[c])\n",
    "        return len(peoples) - maxcnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        lan = defaultdict(set)\n",
    "        cnt = defaultdict(int)\n",
    "        learn = mx = 0\n",
    "        \n",
    "        for i, x in enumerate(languages):\n",
    "            for y in x:\n",
    "                lan[i + 1].add(y)\n",
    "        \n",
    "        needlearn = 0\n",
    "        s = set()\n",
    "        for a, b in friendships:\n",
    "            if all(x not in lan[b] for x in lan[a]):\n",
    "                s.add(a)\n",
    "                s.add(b)\n",
    "                \n",
    "        for person in s:\n",
    "            for x in lan[person]:\n",
    "                cnt[x] += 1\n",
    "                if cnt[x] > mx:\n",
    "                    learn = x\n",
    "                    mx = cnt[x]\n",
    "        \n",
    "        ans = 0\n",
    "        for person in s:\n",
    "            if learn not in lan[person]:\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1 3 4 6 9 12\n",
    "    # {(2, 4), (3, 8), (0, 4), (1, 2), (0, 3), (3, 10), (2, 3), (2, 6), (4, 11), (3, 11)}\n",
    "    # [2, 0, 4, 0, 0, 0, 0, 0, 1, 0, 1, 2, 0]\n",
    "    #  0  1  2  3  4  5  6  7  8  9  10 11 12\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        m = len(languages)\n",
    "        languages = [set(lang) for lang in languages]\n",
    "        friends = set()\n",
    "        for pair in friendships:\n",
    "            if languages[pair[0] - 1] & languages[pair[1] - 1]: continue\n",
    "            friends.add((pair[0] - 1, pair[1] - 1))\n",
    "        ans = 0x3f3f3f3f\n",
    "        for i in range(1, n + 1):\n",
    "            total = len(friends)\n",
    "            vis = [False] * m\n",
    "            for pair in friends:\n",
    "                if i in languages[pair[0]]:\n",
    "                    vis[pair[0]] = True \n",
    "                if i in languages[pair[1]]:\n",
    "                    vis[pair[1]] = True \n",
    "            cnt = 0\n",
    "            for pair in friends:\n",
    "                if not vis[pair[0]]:\n",
    "                    cnt += 1\n",
    "                    vis[pair[0]] = True\n",
    "                if not vis[pair[1]]:\n",
    "                    cnt += 1\n",
    "                    vis[pair[1]] = True\n",
    "            ans = min(ans, cnt)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        c=collections.Counter()\n",
    "        ls=[set()]\n",
    "        for i in languages:\n",
    "            ls.append(set(i))\n",
    "        s=set()\n",
    "        for a,b in friendships:\n",
    "            if ls[a]&ls[b]:\n",
    "                continue\n",
    "            s.add(a)\n",
    "            s.add(b)\n",
    "        for i in list(s):\n",
    "            for j in languages[i-1]:\n",
    "                c[j]+=1\n",
    "        if not c:\n",
    "            return len(list(s))\n",
    "        return len(list(s))-max(c[j] for j in c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 枚举\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        ability = [set(lang) for lang in languages]\n",
    "        friendships = [[x, y] for x, y in friendships if len(ability[x - 1].intersection(ability[y - 1])) == 0]\n",
    "        ans = len(languages)\n",
    "        for i in range(1, n + 1):\n",
    "            cur = set()\n",
    "            for x, y in friendships:\n",
    "                if i not in ability[x - 1]:\n",
    "                    cur.add(x)\n",
    "\n",
    "                if i not in ability[y - 1]:\n",
    "                    cur.add(y)\n",
    "\n",
    "            ans = ans if ans < len(cur) else len(cur)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        m = len(languages)\n",
    "        languages = [set(lang) for lang in languages]\n",
    "        mapping = {}\n",
    "        peoples = set()\n",
    "        maxcnt = 0\n",
    "        for a, b in friendships:\n",
    "            if(len(languages[a-1] & languages[b-1]) == 0):\n",
    "                if(a-1 not in peoples):\n",
    "                    peoples.add(a-1)\n",
    "                    for c in languages[a-1]:\n",
    "                        if(c not in mapping):\n",
    "                            mapping[c] = 0\n",
    "                        mapping[c] += 1\n",
    "                        maxcnt = max(maxcnt,mapping[c])\n",
    "                if(b-1 not in peoples):\n",
    "                    peoples.add(b-1)\n",
    "                    for c in languages[b-1]:\n",
    "                        if(c not in mapping):\n",
    "                            mapping[c] = 0\n",
    "                        mapping[c] += 1\n",
    "                        maxcnt = max(maxcnt,mapping[c])\n",
    "        return len(peoples) - maxcnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 枚举\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        ability = [set(lang) for lang in languages]\n",
    "        friendships = [[x, y] for x, y in friendships if len(ability[x - 1].intersection(ability[y - 1])) == 0]\n",
    "        ans = len(languages)\n",
    "        for i in range(1, n + 1):\n",
    "            cur = set()\n",
    "            for x, y in friendships:\n",
    "                if i not in ability[x - 1]:\n",
    "                    cur.add(x)\n",
    "\n",
    "                if i not in ability[y - 1]:\n",
    "                    cur.add(y)\n",
    "\n",
    "            ans = ans if ans < len(cur) else len(cur)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        # 筛出语言无交集的朋友\n",
    "        languages = [0] + list(map(set, languages))\n",
    "        gays = set()\n",
    "        for sb1, sb2 in friendships:\n",
    "            if not languages[sb1] & languages[sb2]:\n",
    "                gays.add(sb1)\n",
    "                gays.add(sb2)\n",
    "        # 统计这些人中最流行的语言\n",
    "        d = Counter([language for sb in gays for language in languages[sb]])\n",
    "        popular = max(d.values()) if d.values() else 0\n",
    "        # 总人数-最流行\n",
    "        return len(gays) - popular"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, ls: List[List[int]], fs: List[List[int]]) -> int:\n",
    "        sls = [set(x) for x in ls]\n",
    "        need = [f for f in fs if len(sls[f[0] - 1] & sls[f[1] - 1]) == 0]\n",
    "        ret = len(ls)\n",
    "        for i in range(1, n + 1):\n",
    "            c = set()\n",
    "            for x, y in need:\n",
    "                if i not in sls[x - 1]:\n",
    "                    c.add(x)\n",
    "                if i not in sls[y - 1]:\n",
    "                    c.add(y)\n",
    "            ret = min(ret, len(c))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        yu = [0] +list(map(set, languages))\n",
    "        s=set()\n",
    "        for a,b in friendships:\n",
    "            if not yu[a]&yu[b]:\n",
    "                s.add(a)\n",
    "                s.add(b)\n",
    "        if len(s)==0:return 0\n",
    "        c=Counter()\n",
    "        for w in s:c+= Counter(yu[w])\n",
    "        return len(s) -c.most_common(1)[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        # 将每个用户掌握的语言转化为集合方便查询\n",
    "        languages = [set(lang) for lang in languages]\n",
    "        \n",
    "        # 寻找无法沟通的好友对\n",
    "        no_communication = []\n",
    "        for u, v in friendships:\n",
    "            if not languages[u-1] & languages[v-1]:\n",
    "                no_communication.append((u, v))\n",
    "        \n",
    "        # 如果所有好友对都可以沟通，则返回 0\n",
    "        if not no_communication:\n",
    "            return 0\n",
    "        \n",
    "        # 对于每一种语言，统计如果选择这种语言，需要教授的用户数量\n",
    "        min_teach = float('inf')\n",
    "        for lang in range(1, n+1):\n",
    "            to_teach = set()\n",
    "            for u, v in no_communication:\n",
    "                if lang not in languages[u-1]:\n",
    "                    to_teach.add(u)\n",
    "                if lang not in languages[v-1]:\n",
    "                    to_teach.add(v)\n",
    "            min_teach = min(min_teach, len(to_teach))\n",
    "        \n",
    "        return min_teach\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        ls=[set(l) for l in languages]\n",
    "        \n",
    "        qs=set()\n",
    "        for fs in friendships:\n",
    "            f1,f2=fs \n",
    "            for lg in languages[f1-1]:\n",
    "                if lg in ls[f2-1]:\n",
    "                    break \n",
    "            else:\n",
    "                qs.update(fs)\n",
    "        ans=inf     \n",
    "        for i in range(1,n+1):\n",
    "            t=0\n",
    "            for e in qs:\n",
    "                if i not in ls[e-1]:\n",
    "                    t+=1\n",
    "            ans=min(ans,t)\n",
    "        return ans\n",
    "        \n",
    "         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        yu = [0]+languages\n",
    "        st = [set()] + [set(x) for x in languages]\n",
    "        s = set()\n",
    "        for i, j in friendships:\n",
    "            if not st[i] & st[j]:\n",
    "                s.add(i)\n",
    "                s.add(j)\n",
    "        if not s:\n",
    "            return 0\n",
    "        c = Counter()\n",
    "        for i in s:\n",
    "            c += Counter(yu[i])\n",
    "        return len(s) - c.most_common(1)[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "        g = defaultdict(set)\n",
    "        for i, x in enumerate(languages):\n",
    "            g[i+1] = set(x)\n",
    "        lst = []\n",
    "        for x, y in friendships:\n",
    "            if not (g[x] & g[y]): lst.append((x, y))\n",
    "        for i in range(1, 1+n):\n",
    "            s = set()\n",
    "            for x, y in lst:\n",
    "                if i not in g[x]: s.add(x)\n",
    "                if i not in g[y]: s.add(y)\n",
    "            ans = min(ans, len(s))  \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\r\n",
    "        mp = set()\r\n",
    "        record = defaultdict(set)\r\n",
    "        for i, ls in enumerate(languages, 1):\r\n",
    "            for l in ls:\r\n",
    "                record[l].add(i)\r\n",
    "        for x, y in friendships:\r\n",
    "            f = False \r\n",
    "            for lx in languages[x - 1]:\r\n",
    "                for ly in languages[y - 1]:\r\n",
    "                    if lx == ly:\r\n",
    "                        f = True \r\n",
    "            if not f:\r\n",
    "                mp.add(x) \r\n",
    "                mp.add(y)\r\n",
    "        res = inf \r\n",
    "        for l in range(1, n + 1):\r\n",
    "            tot = 0\r\n",
    "            for x in mp:\r\n",
    "                if x not in record[l]:\r\n",
    "                    tot += 1\r\n",
    "            res = min(res, tot) \r\n",
    "        return res \r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "     \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n",
    "        learned_set = [set() for _ in range(n)]\n",
    "        for user_id, user_language in enumerate(languages):\n",
    "            for language in user_language:\n",
    "                learned_set[language - 1].add(user_id)\n",
    "        \n",
    "        user_set = set()\n",
    "        for x, y in friendships:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            flag = False\n",
    "            for language in range(n):\n",
    "                if x in learned_set[language] and y in learned_set[language]:\n",
    "                    flag = True\n",
    "                    break\n",
    "            \n",
    "            if not flag:\n",
    "                user_set.add(x)\n",
    "                user_set.add(y)\n",
    "\n",
    "        language_cnt = {}\n",
    "        for user in user_set:\n",
    "            for language in languages[user]:\n",
    "                language_cnt[language] = language_cnt.get(language, 0) + 1\n",
    "\n",
    "        if not language_cnt:\n",
    "            return 0\n",
    "\n",
    "        return len(user_set) - max(language_cnt.values())"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
